package com.leetcode.algorithm.y22.m05;

import java.util.List;

/**
 * 120. 三角形最小路径和 https://leetcode.cn/problems/triangle/
 * 
 * @author jie.deng
 *
 */
class Question0120Solution02 {

	// DP + 空间复杂度优化
	public int minimumTotal(List<List<Integer>> triangle) {
		if (triangle == null || triangle.size() == 0) {
			return 0;
		}

		int rows = triangle.size();
		int maxCols = triangle.get(rows - 1).size();
		// 状态定义：dp[j]表示到达三角形第x行第j列的最小路径和
		int[] dp = new int[maxCols];
		// 初始化
		dp[0] = triangle.get(0).get(0);

		for (int i = 1; i < rows; i++) {
			int cols = triangle.get(i).size();
			for (int j = cols - 1; j >= 0; j--) {
				// 状态转移方程
				if (j == cols - 1) { // 三角形当前行最后一个元素
					dp[j] = triangle.get(i).get(j) + dp[j - 1];
				} else if (j > 0) { // 三角形当前行中间元素
					dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j - 1]);
				} else { // 三角形当前行第一个元素
					dp[0] = triangle.get(i).get(j) + dp[0];
				}
			}
		}

		// 最小值即最后一行的最小值
		int minimumTotal = dp[0];
		for (int colIdx = 1; colIdx < maxCols; colIdx++) {
			minimumTotal = Math.min(minimumTotal, dp[colIdx]);
		}
		return minimumTotal;
	}

}